Massive polygonal datasets have become widely available, particularly because of advances in data acquisition. Content-authoring tools, such as ZBrush® manufactured by Pixologic of Los Angeles, Calif., enable the creation of extremely detailed art with polygon counts exceeding several hundred million triangles. However, interactive rendering of such massive geometry in computer games or other applications can be impractical due to the performance penalty for vertex throughput and the associated large memory storage requirements. As a result, mesh simplification has been an active area of research. In general, mesh simplification entails transforming an input mesh containing a number of triangles into a simplified mesh having fewer triangles that approximates well the original mesh.
Various mesh simplification algorithms have been devised to decimate a triangle mesh. Some algorithms employ vertex clustering, which involves placing an input mesh into a bounding box, and dividing the box into a grid. In a simplest case, the result is a rectilinear lattice of cubes, with all vertices in a given cube or cell being replaced with a single representative vertex (i.e., clustered). Faces that become degenerate are removed from the resulting simplified mesh. Other mesh simplification algorithms take an iterative approach, in which a series of primitive simplification operations are applied to an input mesh through intermediate simplification stages. Usually, the choice of operations attempts to minimize the incremental error incurred by the operations.
Simplification of massive datasets demands computational efficiency and effective use of available memory. Traditionally, methods developed for mesh simplification and decimation are designed with the CPU architecture and programming model in mind. Consequently, mesh simplification has been a slow, CPU-limited operation performed as a non-interactive process on static meshes.